# 相同的树：https://leetcode-cn.com/problems/same-tree/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        """
            深度遍历， 前序遍历实现。 从上往下比较，不相等直接回溯，返回
            1. 先比较根节点是否相同
            2. 在比较左子树是否相同
            3. 再比较右子树是否相同
        """
        def inorder(node1, node2):
            # 递归终止条件, 要注意写法，为 True的只有这种。到达最后可以回溯返回True， 
            # 像 node1.val == node2.val，这种不能返回True， 要看子节点的比较，直接返回了，递归终止了，还没判断后序子节点呢
            if not node1 and not node2:
                return True
            if not node1 or not node2:
                return False
            if node1.val != node2.val:
                return False

            return inorder(node1.left, node2.left) and inorder(node1.right, node2.right)

        return inorder(p, q)


# 还有广度遍历能实现，层序遍历， 不过好像复杂一些
# 我自己写的
from collections import deque
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        """
            层序遍历： 要记录结构， 左右节点有为 None的，也要记录每行
        """
        queue1, queue2 = deque(), deque()
        queue1.append(p); queue2.append(q)

        while queue1 and queue2:
            n1 = len(queue1); n2 = len(queue2)
            # 1. 如果层数 节点数不等，直接返回False
            if n1 != n2: return False
            temp1, temp2 = [], []
            # p的一层
            for i in range(n1):
                node = queue1.popleft()
                if node:
                    temp1.append(node.val)
                    
                    queue1.append(node.left)
                    queue1.append(node.right)
                else:
                    temp1.append(node)
            # q的一层
            for i in range(n2):
                node = queue2.popleft()
                if node:
                    temp2.append(node.val)
                    
                    queue2.append(node.left)
                    queue2.append(node.right)
                else:
                    temp2.append(node)
            
            # 2. 节点不一样
            if temp1 != temp2: return False
        
        # 3. 最后看看是不是两个queue都为 空了
        return False if queue1 or queue2 else True 


# 上面的写法太麻烦了，补充一个 一个队列的写法， 并且完全没必要分层遍历（多余的for循环，分层）
"""
评论区找的Java版本的。和101号算法题 对称二叉树一样

public boolean isSameTree(TreeNode p, TreeNode q) {
        // 广度优先
        Queue<TreeNode> tmpQueue = new LinkedList<TreeNode>();
        tmpQueue.offer(p);
        tmpQueue.offer(q);
        while(!tmpQueue.isEmpty()){
            p = tmpQueue.poll();
            q = tmpQueue.poll();
            if(p == null && q == null){
                continue;
            }
            if((p == null || q == null) || p.val != q.val){
                return false;
            }
            tmpQueue.offer(p.left);
            tmpQueue.offer(q.left);

            tmpQueue.offer(p.right);
            tmpQueue.offer(q.right);
        }
        return true;
    }

"""
